package SortAlgorithm;

/**
 * @author zxc
 * @date 2023/01/14 09:51
 **/

import LinkedList.ListNode;

/**
 * 题目 ：链表排序
 * 题目详述 ：
 * 给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class SortList_Recursion {
    /**
     * 分析 ：题目条件，在于对于链表进行排序
     * （1）冒泡排序，插入排序等等算法 ：所需要的时间复杂度为O（n * n）;
     *     上述排序的时间复杂度较高，不建议使用
     *     （虽然上述方法的时间复杂度较高，但是若是题目对于时间复杂度没有啥子要求，则可以通过上述算法，暴力地去求解）
     * （2）堆排序 :
     * a.若是数组nums的话，则去构建最小堆（堆中存储数组中的所有元素），将最小堆的堆顶元素依次弹出到nums中，实现数组的排序；
     * b.若是链表list的话，
     * 去链表中寻找某个链表节点元素，都需要从链表的头节点进行遍历，即说明时间复杂度为O（n）；
     * 对比之下，若是去数组中寻找某个数组元素的话，只需要根据数组下标索引去查询即可，说明所需要的时间复杂度为O（1）；
     * ===》 综上所述，我们不可能直接使用链表去实现堆（尝试将长度为n的链表转化为长度为n的数组，从而来实现堆排序，只不过需要消耗O（n）空间）
     * （3）快速排序 ：
     * 由于快速排序随机生成一个数组下标（即，也可以理解为随机的节点编号）
     *      去链表中寻找某个链表节点元素，都需要从链表的头节点进行遍历，即说明时间复杂度为O（n）；
     *      对比之下，若是去数组中寻找某个数组元素的话，只需要根据数组下标索引去查询即可，说明所需要的时间复杂度为O（1）；
     *  ===》 综上所述，为避免在链表中查询某个节点的时间复杂度为O（n）；
     *       我们会选择以某个固定位置的值作为中间值（链表的头结点/尾节点），但是同时带来的问题，就是时间复杂度会退化为O（n * n）；
     * （4）归并排序 ：
     * 主要思想 ：即，将链表分解成若干个子链表；在对于子链表进行排序之后，再次将其合并merge成一个已经排序好的链表；
     * 优势 ：
     * （1）对于链表进行归并排序的话，我们不需要去创建一个辅助链表，只需要将链表截断成若干个子链表即可；
     * （2）同时，若是使用递归来实现归并排序的话，递归调用栈的深度为O（logn） 《===》 所需要消耗的空间复杂度为 ：O（logn）
     */
    public ListNode sortList(ListNode head) {
        // 即，代表了对于子链表来说，所划分出的子链表至少要有2个及以上链表节点
        // 有且仅有两个及以上的链表节点，才能够去进行排序合并操作；
        if(head == null || head.next == null){
            return head;
        }
        // 即，使用head1节点，来存储当前链表所划分的第一个子链表头结点
        ListNode head1 = head;
        // 即，使用head2节点，来存储当前链表所划分的第二个子链表头结点
        ListNode head2 = split(head);

        // 对于当前链表list所划分出来的第一条子链表，进行递归划分子链表
        // 若是当前链表不能再次进行子链表划分的话，即head1 == head1；
        // 若是当前链表还能再次进行子链表划分的话，即返回的是，对于子链表进行排序同时合并成新链表之后，已经排序好的新链表头结点
        head1 = sortList(head1);
        // 对于当前链表list所划分出来的第二条子链表，进行递归划分子链表
        head2 = sortList(head2);

        // 即，上述是对链表进行划分成子链表；
        // 此处，需要将上述所划分的子链表合并merge成一个排序好的链表；（同时，注意的是，返回的是排序好链表的头结点）
        return merge(head1 , head2);

    }
    // merge方法，即创建新链表，来对于子链表中节点排序的结果进行合并存储;
    private ListNode merge(ListNode head1, ListNode head2) {
        // 虚拟头结点，用来存储新创建的链表（新创建的链表，用来存储子链表合并后的结果）
        ListNode dummy = new ListNode(0);
        // 定义一个cur指向dummy虚拟头结点，用来保证虚拟头结点dummy的值不会在之后的合并过程中被修改
        // 即，cur节点，用于构建新链表；
        // （即，所插入的节点都是在cur.next;后同时将cur = cur.next;使得cur随时指向新构建链表的尾节点）
        ListNode cur = dummy;
        // 即，while循环的结束条件为 ：当其中的某个子链表被遍历结束，即退出循环
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                cur.next = head1;
                // head1节点后移
                head1 = head1.next;
            }
            else{
                cur.next = head2;
                //head2节点后移
                head2 = head2.next;
            }
            cur = cur.next;
        }
        // 在while循环结束后，由于子链表中所有元素都是顺序存放的，即只需要将未遍历完的子链表后续节点续接到新创建的链表之后即可
        cur.next = head1 != null ? head1 : head2;
        // 需要注意的是，所需要返回的值，未新构建的链表的头结点（而并不是虚拟头结点dummy）
        return dummy.next;
    }

    // split方法 ：即，用于返回当前链表所划分的第二个子链表头结点;
    /**
     *  需要注意的是，此split方法，
     *  （1）在链表的节点数为奇数时，返回值为 n/2 + 1;(即，代表的是链表中间节点 && 左链表长度 = 右链表长度 + 1)；
     *  （2）在链表的节点数为偶数时，返回值为 n/2 ;(即，左右子链表长度时一致的)
      */
    private ListNode split(ListNode head) {
        // 核心思想 ：使用快慢指针，当快指针遍历到链表尾部时，慢指针所遍历到的基本上就是链表中间
//        ListNode slow = head;
//        ListNode fast = head.next;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        /**
         *  思考 ：为什么fast指针所使用的是 head.next?
         *  原因 ：
         *  即，所需要划分的子链表长度为 n/2（无论原先的链表节点数为奇数还是偶数，都需要满足划分出的第一条子链表长度 >= 第二条子链表长度）
         *  1.若是slow和fast指针都指向链表头结点的话，
         *  （1）同时若是链表节点数为奇数n的话，则slow == n/2 + 1;
         *  （2）同时若是链表节点是偶数n的话，则slow == n/2 + 1;
         *  2.若是slow指针指向头结点，同时fast指针指向头结点的next节点，
         *  （1）同时若是链表节点数为奇数n的话，则slow == n/2 + 1;
         *  （2）同时若是链表节点是偶数n的话，则slow == n/2 ;
         *  3.dummy.next = head;
         *  若是slow指针指向dummy，同时fast指针也指向dummy的话，
         *  （1）同时若是链表节点数为奇数n的话，则slow == n/2 + 1;
         *  （2）同时若是链表节点是偶数n的话，则slow == n/2 ;
         *
         * ===> 综上所述，主要还是偶数的情况，若是fast和slow指针同时指向head节点的话，
         * 那么在链表节点数为偶数情况下，slow指针最后指向的是 n/2 + 1;
         * 但是，我们所需要使得slow指针所指向为 n/2;(因为只有这样子，才能够保证归并排序对于链表的划分，是左右子链表基本大小一致)
         */
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode node = slow.next;
        // 使得slow指针的next指向null，从而实现子链表截断操作；
        // slow指针，所指向的就是所划分出的第一条子链表的尾节点；
        slow.next = null;
        // 返回值为 第二条子链表的头结点
        return node;
    }
    /**
     * 分析 :
     * （1）时间复杂度 ：由于使用的是归并排序，所需要的时间复杂度为：O（nlogn）；
     * （2）空间复杂度 ：由于递归调用栈深度为logn，所以所需要的空间复杂度为O（logn）；
     */
}
